public class test08 {
    class Solution {
        public boolean canPartition(int[] nums) {
            int sum = 0;
            for(int num:nums){
                sum += num;
            }
            if(sum%2 != 0){
                return false;
            }
            int target = sum/2;
            int[][] dp = new int[nums.length][target+1];
            //初始化
            for(int j = nums[0];j<target+1;j++){
                dp[0][j] = nums[0];
            }
            for(int i = 1;i<nums.length;i++){
                for(int j = 0;j<=target;j++){
                    if(j>=nums[i]){
                        //装得下
                        //考虑装不装
                        dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-nums[i]]+nums[i]);
                    }else{
                        //装不下
                        dp[i][j] = dp[i-1][j];
                    }

                }

            }
            return dp[nums.length-1][target]==target;

        }
    }
}
